//打家劫舍
//https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        if(n == 1) return nums.back();
        //dp[i] 表示前i间房子可以获得的最多钱
        vector<int> dp(n);
        dp[0] = nums[0];
        dp[1] = max(dp[0],nums[1]);   
        for(int i = 2; i < n; i++)
        {
            //可以偷或者不偷，取最大值
            dp[i] = max(dp[i - 2] + nums[i],dp[i - 1]);
        }
        return max(dp[n - 1],dp[n - 2]);
    }
};